package com.hss.sort;

public class QuickSort2 {
    public static void main(String[] args) {
        int[] a = new Data().a;
        sort(a, 0, a.length-1);
        Print.printArr(a);
    }


    public static void sort(int[] arr, int left, int right){
        if (left < right){
            int mid = getMid(arr, left, right);
            sort(arr, mid+1, right);

            sort(arr,left,mid-1);
        }

    }

    public static  int getMid(int[] arr, int left, int right){
        int start = left;
        int value = arr[left];

        while (left < right){
            while (left <right && arr[right]>= value){
                right--;
            }

            while (left<right && arr[left] <= value){
                left++;
            }
            swap(arr,left,right);
        }


        swap(arr, left, start);
        return left;

    }


    public static void swap(int[]arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
